Table of Contents
二分查找的原理
二分查找所应用的对象要求是有序的。 比如对一个按升序排好的数组，在其中查找给定值的元素。
查找时每次取正中位置mid = ( low + (high-low) / 2 )， 如果该元素即为所找元素，则查找结束； 如果该元素比所找元素大，则说明该元素右边的元素也必然比所找元素大，所以该元素右边的元素即数组右半部分可以舍去，此时令high = mid - 1。重置查找区间，进行下一趟查找。 同理，如果该元素比所找元素小，则说明该元素左边的元素也必然比所找元素小，所以该元素左边的元素即数组左半部分可以舍去，此时令low = mid + 1。重置查找区间，进行下一趟查找。
二分查找结束的条件是当所搜索的区间为空区间即 low > high时，查找结束，此时如果未找到给定元素在数组中的位置，则说明数组中无给定元素。
示例代码
#include <iostream>
#include <cstdio>
using namespace std;
int Binary_Search(int *p_start, int *p_end, int value)
{
int index = -1;
int length = p_end - p_start;
int low = 0;
int high = length; // 数组末尾元素地址，而非末尾元素之后的地址
int mid;
while (low <= high){
mid = low + (high - low) / 2;
if(*(p_start+mid) == value){
index = mid;
break;
}
else if (*(p_start+mid) > value)
high = mid -1;
else
low = mid + 1;
}
return index;
}
int main()
{
int Array[10] = {1,2,3,4,5,6,7,8,9,10}; // Sorted increasingly Array
// Array 是数组的起始地址
// Array+9是数组末尾元素的地址
// Array+10是数组末尾元素之后的地址
// 如果搜索范围是整个数组，则区间为[Array,Array+9]
printf("The index of 1 is %d\n", Binary_Search(Array,Array+9,1));
printf("The index of 1 is %d\n", Binary_Search(Array+1,Array+9,1));
printf("The index of 10 is %d\n", Binary_Search(Array,Array+9,10));
printf("The index of 10 is %d\n", Binary_Search(Array,Array+8,10));
printf("The index of %d is %d\n", Array[5],Binary_Search(Array+5,Array+5,Array[5]));
return 0;
}
而在实际问题中应用二分法求解的时候，我们需要明确的，其实是在上例中的所谓「数组」也即「搜索区间」。 以下为北京大学在中国大学MOOC开设的算法基础课对应二分法部分内容的练习题。
二分法问题001：派
总时间限制: 1000ms 内存限制: 65536kB
描述 我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。
我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。
请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。
输入 第一行包含两个正整数N和F，1 ≤ N, F ≤ 10 000，表示派的数量和朋友的数量。 第二行包含N个1到10000之间的整数，表示每个派的半径。
输出 输出每个人能得到的最大的派的体积，精确到小数点后三位。
样例输入
3 3
4 3 3
样例输出
25.133
思路 & 代码
/*
本题要找的是量够所有人一人一块的派的最大体积
同样的，可以认为这个最大体积必然存在，且存在于[-∞,+∞]中
缩小区间为[0,半径最大的派的体积]
进行二分查找
*/
#include <iostream>
#include <cstdio>
#define pi 3.1415926535897932
#define EPS 1E-6
using namespace std;
double Divide_Pies(int *pies_R, int N, int F)
{
// N pies, F pieces
double Max_V = -1;
int Max_R = -1;
for (int i = 0; i < N; ++i){
if (pies_R[i] > Max_R)
Max_R = pies_R[i];
}
double high = pi*Max_R*Max_R*1;
double low = 0;
double V; // Present Volume
while ((high - low) > EPS){
V = low + (high - low) / 2;
int count = 0;
for (int i = 0; i < N; ++i){
count = count + int( (pi*pies_R[i]*pies_R[i]*1) / V );
}
if (count < F) // not feasible
high = V;
else{
Max_V = V;
low = V;
}
}
return Max_V;
}
int main()
{
int N, F; // N pies and F friends
scanf("%d %d", &N, &F);
++F; // include myself
int pies_R[N+10];
for (int i = 0; i < N; ++i){
scanf("%d", &pies_R[i]);
}
printf("%.3f\n", Divide_Pies(pies_R,N,F));
return 0;
}
二分法问题002：月度开销
总时间限制: 1000ms 内存限制: 65536kB
描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入 第一行包含两个整数N,M，用单个空格隔开。 接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。 输出 一个整数，即最大月度开销的最小值。 样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
提示 若约翰将前两天作为一个月，第三、四两天作为一个月，最后三天每天作为一个月，则最大月度开销为500。其他任何分配方案都会比这个值更大。
思路 & 代码
/*
本题要找的是开销最多的fajo月开销的最小值
同样的，可以认为这个最小值必然存在，且存在于[-∞,+∞]中
缩小区间为[0,N天总开销]
进行二分查找
*/
#include <iostream>
#include <cstdio>
using namespace std;
int Manage_Expense(int N, int M, int *expense)
{
int Max_fajo = -1;
int sum = 0;
for (int i = 0; i < N; ++i)
sum = sum + expense[i];
int low = 0;
int high = sum;
while (low <= high){
int fajo = low + (high - low) / 2;
//
int i;
sum = 0;
int count = 0;
int day_count = 0;
int sign = 0;
for (i = 0; i < N; ++i){ // 验证是否可以划分求符合要求的M个fajo
sum = sum + expense[i];
++day_count;
if (sum > fajo && day_count == 1){
sign = 1;
break;
}
else if (sum > fajo){
++count;
--i;
sum = 0;
day_count = 0;
}
else if (sum == fajo){
++count;
sum = 0;
}
}
if(sum != 0)
++count;
//
if (count <= M && sign == 0){ // Plausible
Max_fajo = fajo;
high = fajo - 1;
}
else
low = fajo + 1;
}
return Max_fajo;
}
int main()
{
//freopen("D:\\in.txt","r",stdin);
int N, M;
scanf("%d %d", &N, &M);
int expense[N+10];
for (int i = 0; i < N; ++i)
scanf("%d", &expense[i]);
printf("%d\n", Manage_Expense(N, M, expense));
return 0;
}
二分法问题003：Aggressive cows
总时间限制: 1000ms 内存限制: 65536kB
描述 Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入
-
Line 1: Two space-separated integers: N and C
-
Lines 2..N+1: Line i+1 contains an integer stall location, xi
输出
- Line 1: One integer: the largest minimum distance
样例输入
5 3
1
2
8
4
9
样例输出
3
提示 OUTPUT DETAILS:
FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.
Huge input data,scanf is recommended. 来源 USACO 2005 February Gold
思路 & 代码
/*
本题是要找到两头牛之间的最小距离
stalls是划分好的，牛的数量C不大于stalls的数量N，则最小距离必然存在
可以认为说，从-∞到+无穷中必然存在一个值等于我们要找的最小距离
进一步，我们可以把搜索区间从[-∞,+∞]缩小到[0,1000000000]（有序）
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int Aggressive_cows(int N, int C, int *stalls)
{
sort(stalls,stalls+N); // Sort the stall position
int Max_Distance = -1;
int low = 0;
int high = 1000000000;
int D; // Present Distance
while (low <= high){
D = low + (high - low) / 2;
//
int i;
int last_cow = 0;
for (i = 1; i < C; ++i){
int j;
for (j = last_cow; j < N; ++j){
if (stalls[j] - stalls[last_cow] >= D){
last_cow = j;
break;
}
}
if (j == N) // D is not plausible
break;
}
//
if (i < C) // D is not plausible. Namely, D is too large.
high = D - 1;
else{ // D is feasible
Max_Distance = D; // record the feasible distence
low = D + 1; // Try to find a larger feasible distance
}
}
return Max_Distance;
}
int main()
{
int N, C;
scanf("%d %d", &N, &C);
int stalls[N];
for (int i = 0; i < N; ++i)
scanf("%d", &stalls[i]);
printf("%d\n", Aggressive_cows(N,C,stalls));
return 0;
}